//交叉处理

VerticalPosIntOptimizer = function ( pairScoreFunc, initLevels, minLevels ) {
    this.pairScoreFunc = pairScoreFunc;      
                                             

    this.initLevels = initLevels;            // array[int]

    this.maxOfMinlevels = 1;
    if (minLevels) {
        this.maxOfMinlevels = Math.max.apply(null, minLevels);
        if (this.maxOfMinlevels > 1)
            this.minLevels = minLevels;
    }

    var precompute = this.computeComponents();
    this.components = precompute.components;  
    this.crosses    = precompute.crosses;     
};

VerticalPosIntOptimizer.prototype = {

    numberOfLevelsPenalty: function( maxLevelUsed, minRequired, numEdges ) {
        return ( maxLevelUsed - minRequired ) / (numEdges+1);       
    },

    componentScoreFunc: function ( levels, componentID ) {

        var penalty      = 0;
        var maxLevelUsed = 0;
        var minRequired  = 1;

        var component = this.components.getComponentEdges(componentID);

        for (var i = 0; i < component.length; i++) {
            var edge    = component[i];
            if (levels[edge] > maxLevelUsed)
                maxLevelUsed = levels[edge];
            if (this.minLevels && this.minLevels[edge] > minRequired)
                minRequired = this.minLevels[edge];
            var crosses = this.crosses[edge];
            for (var j = 0; j < crosses.length; j++) {
                var intersects = crosses[j];
                if (intersects > edge) {                  
                    penalty += this.pairScoreFunc( edge, intersects, levels[edge], levels[intersects], levels );
                    if (!isFinite(penalty))
                        return penalty;
                }
            }
        }

        var numLevelsPen = this.numberOfLevelsPenalty(maxLevelUsed, minRequired, component.length);
        penalty += numLevelsPen;
        return penalty;
    },

    computeComponents: function () {

        var components = new Complonents();   

        var crosses = [];                     

        var hasToBeAboveForPerfectScore = []; 

        var numEdges = this.initLevels.length;
        for (var i = 0; i < numEdges; i++) {
            crosses[i] = [];
            hasToBeAboveForPerfectScore[i] = [];
        }

        for (var i = 0; i < numEdges-1; i++) {
            for (var j = i+1; j < numEdges; j++) {
                if (this.pairScoreFunc( i, j, 1, 1 ) == Infinity) {  
                    crosses[i].push(j);
                    crosses[j].push(i);

                    var componentI = components.getEdgeComponent(i);
                    var componentJ = components.getEdgeComponent(j);

                    if (componentI === undefined && componentJ === undefined) {
                        components.addToNewComponent(i);
                        components.addToExistingComponent(j, components.getEdgeComponent(i));
                    }
                    else if (componentI !== undefined) {
                        if (componentJ !== undefined) {
                            if (componentI != componentJ) {
                                components.mergeComponents(componentI, componentJ);
                            }
                        } else {
                            components.addToExistingComponent(j, componentI);
                        }
                    } else {
                        components.addToExistingComponent(i, componentJ);
                    }

                    var scoreAbove = this.pairScoreFunc( i, j, 1, 2 );
                    var scoreBelow = this.pairScoreFunc( i, j, 2, 1 );

                    var compID = components.getEdgeComponent(i);
                    components.addRequiredPenaltyToComponent(compID, Math.min( scoreAbove, scoreBelow ));

                    if (scoreAbove < scoreBelow) {
                        hasToBeAboveForPerfectScore[i].push(j);
                    }
                    if (scoreAbove > scoreBelow) {
                        hasToBeAboveForPerfectScore[j].push(i);
                    }
                }
            }
        }


        for (var compID = 0; compID < components.getNumComponents(); compID++) {

            var minNumLevels = 1;
            var minRequired  = 1;
            var minMinLevel  = Infinity;

            var component = components.getComponentEdges(compID);
            for (var i = 0; i < component.length; i++) {
                var edge = component[i];

                if (this.minLevels) {
                    if (this.minLevels[edge] > minRequired)
                        minRequired = this.minLevels[edge];
                    if (this.minLevels[edge] < minMinLevel)
                        minMinLevel = this.minLevels[edge];
                }

                var minForThisEdge = this.minLevels ? this.minLevels[edge] : 1;

                for (var j = 0; j < hasToBeAboveForPerfectScore[edge].length; j++) {
                    var needToBeAboveEdge = hasToBeAboveForPerfectScore[edge][j];
                    var minForOtherEdge = this.minLevels ? this.minLevels[edge] : 1;
                    if (hasToBeAboveForPerfectScore[needToBeAboveEdge].length > 0 && minForOtherEdge == 1)
                        minForOtherEdge++;
                    minForThisEdge = Math.max( minForThisEdge, minForOtherEdge + 1 );
                }

                minNumLevels = Math.max( minNumLevels, minForThisEdge );
            }

            var needExtraLevelsAboveMin = (components.getMinPossiblePenalty(compID) == 0) ? 0 : 1;
            if (!isFinite(minMinLevel)) minMinLevel = 1;
            minNumLevels = Math.max(minNumLevels, minMinLevel + needExtraLevelsAboveMin);

            var penaltyForNumLevelsUsed = this.numberOfLevelsPenalty(minNumLevels, minRequired, component.length);
            components.addRequiredPenaltyToComponent(compID, penaltyForNumLevelsUsed);
        }

        return {"crosses": crosses, "components": components };
    },

    computeVerticalPositions: function( maxFullSearchSize, maxSteps, seed ) {

        this.seed = seed ? seed : 1;

        var bestSoFar = this.initLevels;

        for (var compID = 0; compID < this.components.getNumComponents(); compID++) {

            if ( this.components.getComponentEdges(compID).length <= maxFullSearchSize )
                bestSoFar = this.exhaustiveSearch( compID, bestSoFar );
            else
                bestSoFar = this.simulatedAnnellingOptimizer( compID, bestSoFar, maxSteps );

        }


        return bestSoFar;
    },

    //----------------------------------------------------------------------------------
    exhaustiveSearch: function( componentID, bestSoFar ) {

        var initScore = this.componentScoreFunc(bestSoFar, componentID)

        var result = this.recursiveExhaustiveSearch( componentID, bestSoFar.slice(0), 0, {"values":bestSoFar, "score":initScore} );


        return result.values;
    },

    recursiveExhaustiveSearch: function ( componentID, valuesSoFar, level, bestSoFar ) {

        var component = this.components.getComponentEdges(componentID);

        if (level == component.length) {
            var score = this.componentScoreFunc(valuesSoFar, componentID);
            if (score < bestSoFar.score) {
                bestSoFar.values = valuesSoFar.slice(0);
                bestSoFar.score  = score;
            }
            return bestSoFar;
        }

        var edge = component[level];

        var minValue = 1;
        var maxValue = component.length;

        if (this.minLevels) {
            minValue = this.minLevels[edge];
            maxValue += (minValue - 1);
        }

        for (var i = minValue; i <= maxValue; i++ ) {
            valuesSoFar[edge] = i;

            bestSoFar = this.recursiveExhaustiveSearch( componentID, valuesSoFar, level+1, bestSoFar );

            if (bestSoFar.score == this.components.getMinPossiblePenalty(componentID)) break;
        }

        return bestSoFar;
    },
    //----------------------------------------------------------------------------------


    makeBasicValidAssignment: function ( initLevels, componentID ) {
        var component = this.components.getComponentEdges(componentID);
        var value = 1;

        var newAssignemnt = initLevels.slice(0);
        for (var i = 0; i < component.length; i++) {
            var edge = component[i];
            if (this.minLevels && value < this.minLevels[edge])
                value = this.minLevels[edge];
            newAssignemnt[edge] = value;
            value++; 
        }

        return newAssignemnt;
    },

    computeNeighbour: function ( currentState, componentID, step ) {

        var component = this.components.getComponentEdges(componentID);

        var newState = currentState.slice(0);

        do {
            var edge         = component[ Math.floor(this.random() * component.length) ];
            var oldLevel     = newState[edge];
            var maxUsedLevel = oldLevel;

            var isBelowAll = true;
            var isAboveAll = true;
            var forbidden  = {};
            for (var i = 0; i < this.crosses[edge].length; i++) {
                var crossesWith = this.crosses[edge][i];
                var crossLevel  = newState[crossesWith];
                if (crossLevel > maxUsedLevel)
                    maxUsedLevel = crossLevel;
                forbidden[crossLevel] = true;
                if (crossLevel >= oldLevel)
                    isAboveAll = false;
                if (crossLevel <= oldLevel)
                    isBelowAll = false;
            }
            if (this.minLevels && oldLevel == this.minLevels[edge]) {
                isBelowAll = true;       
            }
        }
        while (isAboveAll && isBelowAll);  

        var newLevel;
        do {
            newLevel = Math.floor(this.random()*(maxUsedLevel + 2));
        }
        while ( newLevel == oldLevel || (isBelowAll && newLevel < oldLevel) || (isAboveAll && newLevel > oldLevel));

        if (forbidden.hasOwnProperty(newLevel)) {
            for (var i = 0; i < component.length; i++) {
                var e = component[i];
                if (newState[e] <= newLevel) {
                    newState[e]++;
                }
            }
        }
        newState[edge] = newLevel;

        this.normalize(newState, component);

        return newState;
    },

    normalize: function( levels, component ) {

        var usedLevels = filterUnique(levels).sort();
        for (var i = usedLevels.length-1; i > 0; i--) {
            if (usedLevels[i] != usedLevels[i-1] + 1) {      
                for (var j = 0; j < component.length; j++) {
                    var e = component[j];
                    if (levels[e] >= usedLevels[i])
                        levels[e]--;
                }
                break;
            }
        }

        for (var i = 0; i < component.length; i++) {
            var edge = component[i];

            var curLevel = levels[edge];
            var minLevel = this.minLevels ? this.minLevels[edge] : 1;

            if (curLevel < minLevel) {
                var adjust = minLevel - curLevel;
                for (var j = 0; j < component.length; j++) {
                    levels[component[j]] += adjust;
                }
            }
        }

        do {
            var changed = false;
            for (var i = 0; i < component.length; i++) {
                var edge = component[i];
                var curLevel = levels[edge];
                var minLevel = this.minLevels ? this.minLevels[edge] : 1;
                if (curLevel > minLevel) {
                    var highestBelow = 0;
                    for (var j = 0; j < this.crosses[edge].length; j++) {
                        var level = levels[this.crosses[edge][j]];
                        if (level < curLevel && level > highestBelow)
                            highestBelow = levels[this.crosses[edge][j]];
                    }
                    if (highestBelow < curLevel - 1) {
                        levels[edge] = highestBelow + 1;
                    }
                }
            }
        } while (changed);

    },

    localOptimization: function( levels, currentScore, componentID, untilFirstImprovement ) {
        return currentScore;
    },

    random: function() {
        var x = Math.sin(this.seed++)*16;
        return x - Math.floor(x);
    },

    doSwitchDuringAnneling: function ( oldScore, newScore, stepsSinceReset ) {
        if (newScore <= oldScore) return true;

        var probability = Math.exp( -(newScore - oldScore) * Math.log((stepsSinceReset+1)*5) );

        if (probability > this.random()) {
            return true;
        }
        return false;
    },

    simulatedAnnellingOptimizer: function ( componentID, bestSoFar, maxSteps ) {

        var bestScore = this.componentScoreFunc(bestSoFar, componentID);

        var bestState = isFinite(bestScore) ? bestSoFar : this.makeBasicValidAssignment(bestSoFar, componentID);
        var bestScore = isFinite(bestScore) ? bestScore : this.componentScoreFunc(bestState, componentID);
        var bestStep  = maxSteps;

        var currentState = bestState;
        var currentScore = bestScore;
        var maxWrongDirection = maxSteps/6;

        var step = maxSteps;
        while (bestScore > this.components.getMinPossiblePenalty(componentID) && step >= 0) {

            if (step < bestStep - maxWrongDirection) {
                currentState = bestState.slice(0);
                currentScore = this.localOptimization(currentState, bestScore, componentID, true);  
                bestStep     = step;
                console.log("[asearch] reset to: " + stringifyObject(currentState) + ", score: " + currentScore + " (@ step = " + (maxSteps - step + 1) + ")");
            }

            var neighbourState = this.computeNeighbour( currentState, componentID, step );
            var neighbourScore = this.componentScoreFunc( neighbourState, componentID );

            if ( this.doSwitchDuringAnneling( currentScore, neighbourScore, bestStep - step ) ) {
                currentState = neighbourState;
                currentScore = neighbourScore;
            }

            if (currentScore < bestScore) {
                console.log("[asearch] New best: " + stringifyObject(currentState) + ", score: " + currentScore + " (@ step = " + (maxSteps - step + 1) + ")");
                bestState = currentState.slice(0);
                bestScore = currentScore;
                bestStep  = step;
            }

            step--;
        }

        bestScore = this.localOptimization(bestState, bestScore, componentID);
        console.log("[asearch] Final optimized best: " + stringifyObject(bestState) + ", score: " + bestScore);

        return bestState;
    }
};


Complonents = function() {
    this.components         = []; // arrat[arrat[int]] 
    this.minPossiblePenalty = []; // array[double]     

    this.edgeComponents = [];  // array[int] 
};

Complonents.prototype = {
    getNumComponents: function() {
        return this.components.length;
    },

    getComponentEdges: function(componentID) {
        return this.components[componentID];
    },

    getEdgeComponent: function( edge ) {
        return this.edgeComponents[edge];
    },

    addToNewComponent: function( edge ) {
        this.edgeComponents[edge] = this.components.length;
        this.components.push([edge]);   
        this.minPossiblePenalty.push(0);       
    },

    addToExistingComponent: function( edge, componentID) {
        this.components[componentID].push(edge);
        this.edgeComponents[edge] = componentID;
    },

    mergeComponents: function( component1, component2) {
        if (component1 == component2)
            return;
        var minID = Math.min(component1, component2);
        var maxID = Math.max(component1, component2);

        for (var i = 0; i < this.components[maxID].length; i++) {
            var edge = this.components[maxID][i];
            this.addToExistingComponent(edge, minID);
        }

        this.minPossiblePenalty[minID] += this.minPossiblePenalty[maxID];

        this.components.splice(maxID,1);
        this.minPossiblePenalty.splice(maxID,1);
    },

    addRequiredPenaltyToComponent: function( componentID, penalty ) {
        this.minPossiblePenalty[componentID] += penalty;
    },

    getMinPossiblePenalty: function( componentID ) {
        return this.minPossiblePenalty[componentID];
    }
};

